| 1. |
- Larsson, Joel, 1987-
(author)
-
On random satisfiability and optimization problems
- 2018
-
Doctoral thesis (other academic/artistic)abstract
- In Paper I, we study the following optimization problem: in the complete bipartite graph where edges are given i.i.d. weights of pseudo-dimension q>0, find a perfect matching with minimal total weight. The generalized Mézard-Parisi conjecture states that the limit of this minimum exists and is given by the solution to a certain functional equation. This conjecture has been confirmed for q=1 and for q>1. We prove it for the last remaining case 0<q<1.In Paper II, we study generalizations of the coupon collector problem. Versions of this problem shows up naturally in various context and has been studied since the 18th century. Our focus is on using existing methods in greater generality in a unified way, so that others can avoid ad-hoc solutions.Papers III & IV concerns the satisfiability of random Boolean formulas. The classic model is to pick a k-CNF with m clauses on n variables uniformly at random from all such formulas. As the ratio m/n increases, the formulas undergo a sharp transition from satisfiable (w.h.p.) to unsatisfiable (w.h.p.). The critical ratio for which this occurs is called the satisfiability threshold.We study two variations where the signs of variables in clauses are not chosen uniformly. In paper III, variables are biased towards occuring pure rather than negated. In paper IV, there are two types of clauses, with variables in them biased in opposite directions. We relate the thresholds of these models to the threshold of the classical model.
|
|
| 2. |
- Pham, Lan Anh, 1991-
(author)
-
On avoiding and completing colorings
- 2019
-
Doctoral thesis (other academic/artistic)abstract
- All of my papers are related to the problem of avoiding and completing an edge precoloring of a graph. In more detail, given a graph G and a partial proper edge precoloring φ of G and a list assignment L for every non-colored edge of G, can we extend φ to a proper edge coloring of G which avoids L? In Paper I, G is the d-dimensional hypercube graph Qd, a partial proper edge precoloring φ and a list assignment L must satisfy certain sparsity conditions. Paper II still deals with the hypercube graph Qd, but the list assignment L for every edge of Qd is an empty set and φ must be a partial proper edge precoloring of at most d-1 edges. In Paper III, G is a (d,s)-edge colorable graph; that is G has a proper d-edge coloring, where every edge is contained in at least s-1 2-colored 4-cycles, L must satisfy certain sparsity conditions and we do not have a partial proper edge precoloring φ on edges of G. The problem in Paper III is also considered in Paper IV and Paper V, but here G can be seen as the complete 3-uniform 3-partite hypergraph K3n,n,n, where n is a power of two in paper IV and n is an even number in paper V.
|
|
